package basic.courseLearn03.problem;

import org.junit.Test;
import basic.utils.CommonUtil;

import java.util.Comparator;
import java.util.PriorityQueue;

public class KSort {

    @Test
    public void test(){
        int[] arr = new int[]{1,2,3,6,5,4,7};
        arr=kSort(arr,4);
        System.out.println(CommonUtil.printArray(arr));
    }

    //几乎有序的数组进行排序
    public int[] kSort(int[] arr,int k){
        if (arr.length<=k){     //普通排序即可,从小到大
            PriorityQueue<Integer> heap = new PriorityQueue<>(new  MyComparator());     //大根堆
            for (int i = 0; i < arr.length; i++) {
                heap.add(arr[i]);
            }
            for (int i = 0; i < arr.length; i++) {
                arr[arr.length-i-1] = heap.poll();
            }
            return arr;
        }

        PriorityQueue<Integer> heap = new PriorityQueue<>();    //默认小根堆

        for (int i = 0; i < k; i++) {
            heap.add(arr[i]);
        }

        for (int i = 0; i < arr.length; i++) {      //利用小根堆，逐个填充最小值
            arr[i]=heap.poll();
            if(i+k< arr.length){
                heap.add(arr[i+k]);
            }
        }
        return arr;
    }



    private class MyComparator implements Comparator<Integer>{

        @Override
        public int compare(Integer o1, Integer o2) {
            //小于0：o1   大于0：o2    等于0：随意
            return o2-o1;
        }
    }






}
